package edu.colorado.core;

import java.io.Serializable;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

import edu.colorado.core.Game.Level;

public class Algorithm implements Serializable /* An object of this class has to be created at the start of a game and that object will only be destroyed when the game is finished (it has to be saved during game save )*/
{
    private static final long serialVersionUID = -8270447594968691578L;

    static final Map<Level, Integer> LIMITS;

    static {
        LIMITS = new HashMap<Level, Integer>();
        LIMITS.put(Level.Easy, 1);
        LIMITS.put(Level.Medium, 3);
        LIMITS.put(Level.Hard, 5);
    }

    public static final Integer HUMAN = 0, DEVICE = 1, NONEOFTHETWO = 2;
    
    public static final Integer INT_MAX = 1000;
    
    public static final Integer numToConnect = 4;

    public static final Integer winNumber = 1 << numToConnect;
    
    public static final Integer winPlaces = 69;
    
    private Level level;
    Integer map[][][];
    Integer dropOrder[];
    Integer width, height;
    GameStateStack gameStateStack;
    GameState currentState;

    public Algorithm(Level level, Board board)
    {
        this.level = level;
        initializeAlgorithmVariables(board);
    }

    void initializeAlgorithmVariables(Board board)
    {
        Integer i;
        Integer column;

        width = board.getWidth();
        height = board.getHeight();

        currentState = new GameState(board);
        gameStateStack = new GameStateStack();
        gameStateStack.push(currentState);

        map = new Integer[width][height][17]; // contains the "win areas" board[i][j] is member of
        initializeMap();

        /* decide search position order, it is shown to be the best to start from the middle */
        dropOrder = new Integer[7];

        column = (width-1) / 2;
        for (i=1; i<=width; i++)
        {
            dropOrder[i-1] = column;
            column += ((i%2)!=0? i : -i);
        }

    } // end of initializeAlgorithmVariables()


    void initializeMap()
    {
        Integer i, j, k, x;
        Integer winIndex = 0;

        /************************** Initialize map[][] ************************/
        for(i=0; i<width; i++)
        {
            for(j=0; j<height; j++)
            {
                map[i][j][0] = -1;
            }
        }

        // Fill in the horizontal win positions
        for(i=0; i<height; i++)
        {
            for(j=0; j<width-numToConnect+1; j++)
            {
                for (k=0; k<numToConnect; k++)
                {
                    for(x=0; map[j+k][i][x] != -1; x++)
                    {
                    }

                    map[j+k][i][x++] = winIndex;
                    map[j+k][i][x] = -1;
                }
                winIndex ++;
            }
        }


        // Fill in the vertical win positions
        for (i=0; i<width; i++)
        {
            for (j=0; j<height-numToConnect+1; j++)
            {
                for (k=0; k<numToConnect; k++)
                {
                    for (x=0; map[i][j+k][x] != -1; x++)
                    {
                    }

                    map[i][j+k][x++] = winIndex;
                    map[i][j+k][x] = -1;
                }

                winIndex++;
            }
        }

        // Fill in the forward diagonal win positions
        for (i=0; i<height-numToConnect+1; i++)
        {
            for (j=0; j<width-numToConnect+1; j++)
            {
                for (k=0; k<numToConnect; k++)
                {
                    for (x=0; map[j+k][i+k][x] != -1; x++)
                    {
                    }

                    map[j+k][i+k][x++] = winIndex;
                    map[j+k][i+k][x] = -1;
                }

                winIndex++;
            }
        }

        // Fill in the backward diagonal win positions
        for (i=0; i<height-numToConnect+1; i++)
        {
            for (j=width-1; j>=numToConnect-1; j--)
            {
                for (k=0; k<numToConnect; k++)
                {
                    for (x=0; map[j-k][i+k][x] != -1; x++)
                    {
                    }

                    map[j-k][i+k][x++] = winIndex;
                    map[j-k][i+k][x] = -1;
                }

                winIndex++;
            }
        }

    }

    Integer other(Integer player)
    {
        return player ^ 1;
    }

    void pushState()
    {
        GameState oldState, newState;

        oldState = new GameState(gameStateStack.top());
        newState = new GameState(oldState);

        gameStateStack.push(newState);

        currentState = newState;
    }

    void popState()
    {
        currentState = gameStateStack.pop();
    }


    Integer evaluateGameState(Integer player, Integer level, Integer alpha, Integer beta)
    {
        if(currentState.winner == player)
        {
            return INT_MAX - gameStateStack.size(); // ??
        }
        else if(currentState.winner == other(player))
        {
            return -(INT_MAX - gameStateStack.size()); // ??
        }
        else if(currentState.board.getNumOfPieces() == width*height)    // tie
        {
            return 0;
        }
        else if(level == gameStateStack.size())
        {
            return playerAdvantage(player);
        }
        else
        {
            Integer best = -INT_MAX;
            Integer maxab = alpha;
            for(Integer i=0; i<width; i++)
            {
                if(currentState.board.getBoardState()[dropOrder[i]][height-1] != NONEOFTHETWO)
                {
                    continue; /* since the column is full*/
                }

                pushState();
                dropPiece(other(player), dropOrder[i]);
                Integer goodness = evaluateGameState(other(player), level, -beta, -maxab);
                if(goodness > best)
                {
                    best = goodness;
                    if(best > maxab)
                    {
                        maxab = best;
                    }
                }
                popState();
                if(best > beta)
                {
                    break;
                }
            }

            return -best;
        }

    }

    Integer dropPiece(Integer player, Integer column) // puts a piece in column, returns the row where the piece was dropped
    {
        Integer y = 0;

        while(currentState.board.getPiece(column, y) != NONEOFTHETWO && ++y < height)
        {
        }

        if(y == height)
        {
            return -1;
        }

        currentState.board.putPiece(column, y, player);
        updateScore(player, column, y);

        return y;
    }


    void updateScore(Integer player, Integer x, Integer y)
    {
        Integer i;
        Integer winIndex;
        Integer playerScoreToBeAdded = 0, opponentScoreToBeSubtracted = 0;
        Integer otherPlayer = other(player);

        for(i=0; map[x][y][i]!=-1; i++)
        {
            winIndex = map[x][y][i];
            playerScoreToBeAdded += currentState.scoreArray[player][winIndex];
            opponentScoreToBeSubtracted += currentState.scoreArray[otherPlayer][winIndex];

            currentState.scoreArray[player][winIndex] <<= 1;
            currentState.scoreArray[otherPlayer][winIndex] = 0;

            if(currentState.scoreArray[player][winIndex]==winNumber)
            {
                if(currentState.winner == NONEOFTHETWO)
                {
                    currentState.winner = player;
                }
            }

        }

        currentState.score[player] += playerScoreToBeAdded;
        currentState.score[otherPlayer] -= opponentScoreToBeSubtracted;
    }

    Integer playerAdvantage(Integer playerNumber)
    {
        if(playerNumber == DEVICE)
        {
            return currentState.score[DEVICE] - currentState.score[HUMAN];
        }
        else
        {
            return currentState.score[HUMAN] - currentState.score[DEVICE];
        }
    }

    Integer realPlayer(Integer x)
    {
        return x & 1;
    }


    Integer decideMove(Integer player)
    {
        Integer bestColumn = -1, goodness = 0, bestWorst = -INT_MAX;
        Integer numOfEqual = 0, realPlayer, currentColumn, result;


        realPlayer = realPlayer(player);

        if(currentState.board.getNumOfPieces() == 1 && currentState.board.getBoardState()[3][0] != NONEOFTHETWO)
        {
            return 3;
        }

        /* simulate a move in each column and evaluate the result */
        for(Integer i=0; i<width; i++)
        {
            pushState();
            currentColumn = dropOrder[i];

            result = dropPiece(realPlayer, currentColumn);

            if(result < 0)
            {
                popState();
                continue;
            }
            else if(currentState.winner == realPlayer)
            {
                bestColumn = currentColumn;
                popState();
                break;
            }
            else
            {
                goodness = evaluateGameState(realPlayer, LIMITS.get(level), -INT_MAX, -bestWorst);
            }

            if(goodness > bestWorst)
            {
                bestWorst = goodness;
                bestColumn = currentColumn;
                numOfEqual = 1;
            }
            else if (goodness == bestWorst) // two moves are equally good
            {
                numOfEqual ++;

                // pick one of the two moves reandomly
                Random generator = new Random();
                if(generator.nextInt() % numOfEqual == 0)
                {
                    bestColumn = currentColumn;
                }
            }

            popState();
        }

        if(bestColumn >= 0)
        {
            return bestColumn;
        }


        return bestColumn;
    }

    boolean isWinner(Integer player)
    {
        return (currentState.winner == player);
    }

    boolean isTie()
    {
        return (currentState.board.getNumOfPieces() == width*height && currentState.winner == NONEOFTHETWO);
    }


    void printCurrentBoard()
    {
        currentState.board.display();
    }
}
